package 牛客.树;
/*
 * @Author   helen
 * @Date     2021/4/11 10:00
 * @Descriptions
            给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
            示例1
                输入    [3,5,1,6,2,0,8,#,#,7,4],5,1
                返回值   3
 */



public class 二叉数的两个节点的最低公共祖先 {
    public int lowestCommonAncestor (BTreeNode<Integer> root, int o1, int o2) {
        // write code here
        if(root == null)
            return -1;
        if(root.data == o1 || root.data == o2)
            return root.data;

        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);

        if(left == -1)
            return right;
        if(right == -1)
            return left;
        return root.data;
    }

    public static void main(String[] args) {
        二叉数的两个节点的最低公共祖先 obj = new 二叉数的两个节点的最低公共祖先();
        BTree<Integer> bTree = new BTree<>();
//        for (int i = 0; i < 10; i++) {
//            bTree.RandomCreatTree(bTree.root, i);
//        }
        bTree.root = new BTreeNode<>(0);
        bTree.root.left = new BTreeNode<>(1);
        bTree.root.right = new BTreeNode<>(2);
        bTree.root.left.left = new BTreeNode<>(3);
        bTree.root.left.right = new BTreeNode<>(4);
        bTree.root.right.left = new BTreeNode<>(5);
        bTree.root.right.right = new BTreeNode<>(6);
        bTree.root.left.left.left = new BTreeNode<>(7);
        int result = obj.lowestCommonAncestor(bTree.root, 3, 5);
        System.out.println(result);
    }
}
